package com.leetcode.partition1;

/**
 * @author `RKC`
 * @date 2021/10/19 19:22
 */
public class LC74搜索二维矩阵 {

    public static boolean searchMatrix(int[][] matrix, int target) {
        //二分使用转化一维进行操作
        int left = 0, right = matrix.length * matrix[0].length - 1;
        while (left <= right) {
            int[] mid = getPosition(matrix, (left + right) >>> 1);
            if (left == right) return matrix[mid[0]][mid[1]] == target;

            if (matrix[mid[0]][mid[1]] < target) {
                left = mid[0] * matrix[0].length + mid[1] + 1;
            } else if (matrix[mid[0]][mid[1]] > target) {
                right = mid[0] * matrix[0].length + mid[1];
            } else {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
        System.out.println(searchMatrix(matrix, 17));
    }

    private static int[] getPosition(int[][] matrix, int index) {
        //将一维索引转化为矩阵索引
        int col = matrix[0].length;
        return new int[]{index / col, index % col};
    }
}
